package com.sicheng.lc.周赛.分类.dp.数位;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/17 20:11
 */
public class x出现的次数 {
    //https://leetcode.cn/problems/number-of-2s-in-range-lcci/

    static int[] pow = new int[10];
    static {
        pow[0] = 1;
        for (int i = 1; i < 10; i++) {
            pow[i] = pow[i - 1] * 10;
        }
    }
    int dgt(int x) {
        int t = 0;
        while (x != 0) {
            x /= 10;
            t++;
        }
        return t;
    }

    // 计算每一位是x时产生的贡献 _____x___
    //  abcdjefg
    //  abcdxefg  x左边是abcd 右边是efg
    //  当固定x到某一位置时
    //     a.左边取 0 ~ abcd-1 时  右边随便填 可以填 0 ~ 999(右边有多少位置可填)
    //     b.左边取 abcd时
    //           b.1   当n与x对应位置的数位 j < x 那就没有情况
    //           b.2                     j== x 右边只能取 0 ~ r
    //           b.3                     j > x  右边可以任意取 0~999
    //       以上分析对 x==0进行特判 如果满足只需要知道 x左边只能从 1开始取 因为0不可以作为数的开头第一位
    int f(int n, int x) {
        int m = dgt(n);
        int res = 0;
        // 从由到左找到 dj的位是数
        for (int i = 1; i <= m; i++) {
            int p = pow[i - 1], l = n / p / 10, r = n % p, dj = n / p % 10;
            if (x > 0)
                res += l * p;
            else if (l > 0)
                res += (l - 1) * p;

            if (x == dj && (x > 0 || l > 0))
                res += r + 1;
            if (x < dj && (x > 0 || l > 0))
                res += p;
        }
        return res;
    }
}
